perm filename V2I.IN[TEX,DEK] blob sn#285505 filedate 1977-05-28 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	folio 397 galley 1
C00020 00003	folio 403 galley 2
C00038 00004	folio 407 galley 3
C00059 00005	folio 411 galley 4
C00081 ENDMK
C⊗;
folio 397 galley 1
    0  {U31}1|'{H10L12M29}W58320#Computer Programming!(Knuth/A-W)!f
    2  . 397!Ch. 4!g.|91(c)|'{A24}|∨4|∨.|∨4|9|∨R|∨A|∨D|∨I|∨X|9|∨C|∨
    5  O|∨N|∨V|∨E|∨R|∨S|∨I|∨O|∨N|'{A12}If men had invented 
   10  arithmetic by counting with their two _sts or 
   18  their eight _ngers, instead of their ten ``digits,'' 
   26  we would never have to worry about writing binary-decimal 
   35  conversion routines. (And we would perhaps never 
   42  have learned as much about number systems.) In 
   50  this section, we shall discuss the conversion 
   57  of numbers from positional notation with one 
   64  radix into positional notation with another radix; 
   71  this process is, of course, most important on 
   79  binary computers when converting decimal input 
   85  data into binary form, and converting binary 
   92  answers into decimal form.|'|≡A|≡.|9|≡T|≡h|≡e 
   97  |≡f|≡o|≡u|≡r |≡b|≡a|≡s|≡i|≡c |≡m|≡e|≡t|≡h|≡o|≡d|≡s|≡.|9|4Bin
   99  ary-decimal conversion is one of the most machine 
  107  dependent operations of all, since engineers 
  113  keep inventing di=erent ways to provide for it 
  121  in the computer hardware. Therefore we shall 
  128  discuss only the general principles involved, 
  134  from which a programmer can select the procedure 
  142  most well suited to his machine.|'!|4|4|4|4We 
  149  shall assume that only nonnegative numbers enter 
  156  into the conversion, since the manipulation of 
  163  signs is easily accounted for.|'!|4|4|4|4Let 
  169  us assume that we are converting from radix |εb 
  178  |πto radix |εB. |π(The methods can also be generalized 
  187  to mixed radix notations, as shown in exercises 
  195  1 and 2.) Most cr*?*?!|4|4|4|4Let us assume that 
  203  we are converting from radix |εb |πto radix |εB. 
  212  |π(The methods can also be generalized to mixed 
  220  radix notations, as shown in exercises 1 and 
  228  2.) Most radix conversion routines are based 
  235  on multiplication and division, using one of 
  242  the following four schemes:|'{A6}!|4|4|4|41)|9Conversion 
  247  of integers (radix point at the right).|'{A12}!Method 
  255  (1a) |εDivision by B (|πusing radix |εb |πarithmetic). 
  263  Given an integer number |εu, |πwe obtain its 
  271  radix |εB |πrepresentation |ε(U|βM|4.|4.|4.|4U|β1U|β0)|βB 
  275  |πas follows:|'{A9}|h|εU|β2|4|∂α=↓|4|"l|"lu/B|"L/B|"L|πmod|4
  277  |εB|E|n|;| U|β0|4|Lα=↓|4u|4|πmod|4|εB>{A6}| U|β1|4|Lα=↓|4|"l
  279  u/B|"L|πmod|4|εB>{A6}| U|β2|4|Lα=↓|4|"l|"lu/B|"L/B|"L|πmod|4
  280  |εB>{A24}|πetc., stopping when |"l.|4.|4.|4|"l|"l|εu/B|"L/B|
  284  "L|4.|4.|4.|4/B|"Lα=↓0.|'{A12}|π!Method (1b) 
  287  |εMultiplication by b (|πusing radix |εB |πarithmetic). 
  294  If |εu |πhas the radix |εb |πrepresentation |ε(u|βm|4.|4.|4.
  301  |4u|β1u|β0)|βb, |πwe can use radix |εB |πarithmetic 
  308  to evaluate the polynomial |εu|βmb|gm|4α+↓|4αo↓|4αo↓|4αo↓|4α
  312  +↓|4u|β1b|4α+↓|4u|β0α=↓u |πin the form|'{A9}|ε{H12}({H10}(.|
  316  4.|4.|4(u|βmb|4α+↓|π!|4|4|4|42)|9Conversion of 
  318  fractions (radix point at the left). Note that 
  326  it is often impossible to express a terminating 
  334  radix |εb |πfraction (|ε0.u|βα_↓|β1u|βα_↓|β2|4.|4.|4.|4u|βα_
  337  ↓|βm)|βb |εexactly |πas a terminating radix |εB 
  344  |πfraction |ε(0.U|βα_↓|β1U|βα_↓|β2|4.|4.|4.|4U|βα_↓|βM)|βB. 
  346  |πFor example, the fraction |f1|d310|) has the 
  353  in_nite binary representation (0.0|40011|40011|40011|4.|4.|4
  356  .)|β2. Therefore methods of rounding the result 
  363  to |εM |πplaces are sometimes of interest.|'{A12}!Method 
  371  (2a) |εMultiplication by B |π(using radix |εb 
  378  |πarithmetic). Given a>fractional number |εu, 
  384  |πwe obtain successive digits of its radix |εB 
  392  |πrepresentation>|ε(.U|βα_↓|β1U|βα_↓|β2|4.|4.|4.)|βB 
  394  |πas follows:|'{A9}|h|εU|βα_↓|β3|4|∂α=↓|4|"l|¬A|¬AuB|¬SB|¬SB
  396  |"L|E|n|;| U|βα_↓|β1|4|Lα=↓|4|"luB|"L>{A4}| U|βα_↓|β2|4|Lα=↓
  398  |4|"l|¬AuB|¬SB|"L>{A4}| U|βα_↓|β3|4|Lα=↓|4|"l|¬A|¬AuB|¬SB|¬S
  399  B|"L>{A24}|πwhere |ε|¬Ax|¬S |πdenotes |εx |πmod 
  405  1|4α=↓|4|εx|4α_↓|4|"lx|"L. |πIf it is desired 
  410  to round the result to |εM |πplaces, the computation 
  419  can be stopped after |εU|βα_↓|βM |πhas been calculated, 
  427  and |εU|βα_↓|βM |πshould be increased by unity 
  434  if |ε|¬A.|4.|4.|¬A|¬AuB|¬S|4.|4.|4.|4B|¬S |πis 
  437  greater than |f1|d32|). (Note, however, that 
  443  this may cause a number of carries to occur, 
  452  which must be incorporated into the answer using 
  460  radix |εB |πarithmetic. Therefore it would be 
  467  simpler to add the constant |f1|d32|)|εB|gα_↓|gM 
  473  |πto the original number |εu |πbefore the calculation 
  481  begins, but this may lead to a terribly incorrect 
  490  answer when |f1|d32|)|εB|gα_↓|gM |πcannot be 
  495  represented exactly as a radix |εb |πnumber inside 
  503  the computer. Note further that it is possible 
  511  for the answer to round up to (1.00|4.|4.|4.|40)|ε|βB, 
  519  |πif |εb|gm|4|¬R|42B|gM.)|'{A12}|π!Method (2b) 
  523  |εDivision by b (|πusing radix |εB |πarithmetic). 
  530  If |εu |πhas the radix |εb |πrepresentation |ε(0.u|βα_↓|β1u|
  537  βα_↓|β2|4.|4.|4.|4u|βα_↓|βm)|βb, |πwe can use 
  541  radix |εB |πarithmetic to evaluate |εu|βα_↓|β1b|gα_↓|g1|4α+↓
  546  |4u|βα_↓|β2b|gα_↓|g2|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4u|βα_↓|βmb|gα
  546  _↓|gm |πin the form|'{A9}{H12}|ε({H10}(.|4.|4.|4(u|βα_↓|βm/b
  550  |4α+↓|4u|β1|βα_↓|βm)/b|4α+↓|4αo↓|4αo↓|4αo↓|4α+↓|4u|βα_↓|β2)/
  550  b|4α+↓|4u|βα_↓|β1{H12}){H10}/b.|;{A9}{H10L12M29}|πCare 
  552  should be taken to control errors which might 
  560  occur due to truncation or rounding in the division 
  569  by |εb; |πthese are often negligible, but not 
  577  always.|'!|4|4|4|4To summarize, Methods (1a), 
  582  (1b), (2a), and (2b) give us two choices for 
  591  a conversion process, depending on whether our 
  598  number is an integer or a fraction. And it is 
  608  certainly possible to convert between integers 
  614  and fractions by multiplying or dividing by an 
  622  appropriate power of |εb |πor |εB; |πtherefore 
  629  there are at least four methods to choose from 
  638  when trying to do a conversion.|'{A12}|≡B|≡.|9|≡S|≡i|≡n|≡g|≡
  644  l|≡e |≡p|≡r|≡e|≡c|≡i|≡s|≡i|≡o|≡n |≡c|≡o|≡n|≡v|≡e|≡r|≡s|≡i|≡o
  646  |≡n|≡.|9|4To illustrate these four methods, let 
  652  us assume that |¬m|¬i|¬x is a binary computer, 
  660  and suppose that we want to convert a binary 
  669  integer |εu |πto a decimal integer, that is, 
  677  |εb|4α=↓|42 |πand |εB|4α=↓|410. |πMethod (1a) 
  682  could be programmed as follows:|'{A9}{H9L11M29}|h|ε|∂|¬1|¬h!
  687  |∂|¬e|¬n|¬t|¬a!|∂|¬a|¬n|¬s|¬w|¬e|¬r|¬,|4|1|¬1!!|∂(rA,|4rX)|4
  687  |¬M|4(|"lrAX/10|"L,|4|1rAX|4|πmod|410).|E|n|;
  688  |L|L|¬e|¬n|¬t|¬1|L|¬0|LSet|4|1|εj|4|¬L|40.>|L|L|¬l|¬d|¬x|L|¬
  689  u>|L|L|¬e|¬n|¬t|¬a|L|¬0|¬|πSet|4|1rAX|4|¬L|4|εu.>
  691  |L|¬1|¬h|L|¬d|¬i|¬v|L|≤$|¬1|¬0|≤$|L|π(rA,|4rX)|4|¬L|4(|"lrAX
  691  /10|"L,|4rAX|4mod|410).>|L|L|¬s|¬t|¬x|L|¬a|¬n|¬s|¬w|¬e|¬r|¬,
  692  |4|¬1|L|εU|βj|4|¬L|4|πrX.>|L|L|¬i|¬n|¬c|¬1|L|¬1|L|εj|4|¬L|4j
  693  |4α+↓|41.>|L|L|¬s|¬r|¬a|¬x|L|¬5|L|πrAX|4|¬L|4rA.>
  695  |L|L|¬j|¬x|¬p|L|¬1|¬b|LRepeat|4|1until|4|1result|4|1is|4|1ze
  695  ro.|J!(1)>{A9}{H10L12M29}This requires 18|εM|4α+↓|44 
  699  |πcycles to obtain |εM |πdigits.|'!|4|4|4|4The 
  705  above method used division by 10, Method (2a) 
  713  uses |εmultiplication |πby 10, so it might be 
  721  a little faster. In order to use Method (2a), 
  730  we must deal with fractions, and this leads to 
  739  an interesting situation. Let |εw |πbe the word 
  747  size of the computer, and assume that |εu|4|¬W|410|gn|4|¬W|4
  754  w. |πWith a single division we can _nd |εq |πand 
  764  |εr, |πwhere|'{A9}|εwuα=↓10|gpq|4α+↓|4r,!!0|4|¬E|4r|4|¬W|410
  766  |gp,|J!(2)|;{A9}|πNow if we apply Method (2a) 
  773  to the fraction |ε(q|4α+↓|41)/w, |πwe will obtain 
  780  the digits of |εu |πfrom left to right, in |εn 
  790  |πsteps, since|'{A9}|ε|↔d10|gn|4|(q|4α+↓|41|d2w|)|↔f|4α=↓|4|
  792  ↔du|4α+↓|4|(10|gn|4α_↓|4r|d2w|)|↔f|4α=↓|4u.|J!(3)|;
  793  {A9}|π(This idea is due to P. A. Samet, |εSoftware#Practice 
  802  and Experience |≡1 (1971), 93<96.)|'|π!|4|4|4|4Here 
  808  is the corresponding |¬m|¬i|¬x program:|'{A9}{H9L11M29}|h|n|
  813  ∂|¬2|¬h!|∂|¬j|¬i|¬n|¬n!|∂|¬a|¬n|¬s|¬w|¬e|¬r|¬,|4|1|¬1!|∂Now|
  813  4|1imagine|4|1radix|4|1point|4|1at|4|1left,|4|1rA|4α=↓|4|εx.
  813  |E|n|;|L|L|¬j|¬o|¬v|L|¬o|¬f|¬l|¬o|L|πEnsure|4|1over⊗ow|4|1is
  814  |4|1o=>|L|L|¬l|¬d|¬a|Lu>|L|L|¬l|¬d|¬x|L|≤$|¬1|¬0|gn|≤$|LrAX|
  816  4|¬L|4|εwu|4α+↓|410|ε|gn.>|π|L|L|¬d|¬i|¬v|L|≤$|¬1|¬0|gn|≤$|L
  817  rA|4|¬L|4|εq|4α+↓|41,|4|πrX|4|¬L|4|εr.>|L|L|¬j|¬o|¬v|L|¬e|¬r
  818  |¬r|¬o|¬r|L|πJump|4|1if|4|1|εu|4|¬R|410|gn.>|L|L|¬e|¬n|¬t|¬1
  819  |L|πn<|¬1|LSet|4|1|εj|4|¬L|4nα_↓1.>|L|¬2|¬h|L|¬m|¬u|¬l|L|≤$|
  820  ¬1|¬0|≤$|L|πNow|4|1imagine|4|1radix|4|1point|4|1at|4|1left,|
  820  4|1rA|4α=↓|4|εx.>|L|L|π|¬s|¬t|¬a|L|¬a|¬n|¬s|¬w|¬e|¬r|¬,|4|¬1
  821  |LSet|4|1|εU|βj|4|¬L|4|"l10x|"L.>|L|L|¬s|¬l|¬a|¬x|L|¬5|Lx|4|
  822  ¬L|4|¬A10x|¬S.>|π|L|L|¬d|¬e|¬c|¬1|L|¬1|L|εj|4|¬L|4j|4α_↓|41.
  823  >|L|L|π|¬j|¬i|¬n|¬n|L|¬2|¬b|LRepeat|4|1for|4|1|εn|4|¬Q|4j|4|
  824  ¬R|40.|J!(4)>{A9}{H10L12M29}|πThis slightly longer 
  828  routine requires |ε16n|4α+↓|419 |πcycles, so 
  833  it is a little faster than (1) if |εn|4α=↓|4M|4|¬R|48; 
  842  |πwhen leading zeroes are present, (1) will be 
  850  faster.|'!|4|4|4|4Program (4) as it stands cannot 
  857  be used to convert integers |εu|4|¬R|410|gm |πwhen 
  864  |ε10|gm|4|¬W|4w|4|¬W|410|gm|gα+↓|g1, |πsince 
  866  we would need to take |εn|4α=↓|4m|4α+↓|41. |πIn 
  873  this case we can obtain the leading digit of 
  882  |εu |πby computing |ε|"lu/10|gm|"L; |πthen |εu 
  888  |πmod 10|ε|gm |πcan be converted as above with 
  896  |εn|4α=↓|4m.|'|π!|4|4|4|4The fact that the answer 
  902  digits are obtained from left to right may be 
  911  an advantage in some applications (e.g., when 
  918  typing out the answer one digit at a time). Thus 
  928  we see that a fractional method can be used for 
  938  conversion of integers, although the use of inexact 
  946  division makes a little bit of numerical analysis 
  954  necessary.|'!|4|4|4|4A modi_cation of Method 
  959  (1a) can be used to avoid division by 10, by 
  969  replacing it with two multiplications. It is 
  976  worth mentioning this modi_cation here, because 
  982  radix conversion is often done by small ``satellite'' 
  990  computers which have no division capability. 
  996  If we let |εx |πbe an approximation to |f1|d310|), 
 1005  so that |f1|d310|)|4|¬W|4x|4|¬W|4|f1|d310|)|4α+↓|41/|εw, 
 1008  |πit is easy to prove (see exercise 7) that |ε|"lux|"L|4α=↓|
 1017  4|"lu/10|"L |πor |ε|"lu/10|"L|4α+↓|41, |πso long 
 1022  as |ε0|4|¬E|4u|4|¬W|4w. |πTherefore, if we compute 
 1028  |εu|4α_↓|410|"lux|"L, |πwe will be able to determine 
 1035  the value of |ε|"lu/10|"L:|'{A9}|ε|"lu/10|"L|4α=↓|4|↔A|(|"lu
 1039  x|"L,!|4|4|4|4!!|πif!!|εu|4α_↓|410|"lux|"L|4|¬R|40;|d5|"lux|
 1039  "L|4α_↓|41,!!|πif!!|εu|4α_↓|410|"lux|"L|4|¬W|40.|)|J!(5)|;
 1040  |Hβ*?*?*?*?
folio 403 galley 2
 2301  {U0}{H10L1
 2309  2M29}|π58320#Computer Programming!(Knuth/Addison/Wesley)!f. 
 2311  403!ch. 4!g. 2(c)|'{A6}This procedure simultaneously 
 2317  determines |εu |πmod|410. A |¬m|¬i|¬x program 
 2323  for conversion using this idea appears in exercise 
 2331  8; it requires about 33 cycles per digit.|'!|9|7The 
 2340  procedure represented by (5) can be used e=ectively 
 2348  even if the computer has no built-in multiplication 
 2356  instruction, since multiplication by 10 consists 
 2362  of two shifts and one addition (10|4α=↓|42|g3|4α+↓|42), 
 2369  and multiplication by |f1|d310|) can also be 
 2376  done by combining a few shifting and adding operations 
 2385  judiciously (see exercise 9).|'!|9|7Method (1b) 
 2391  could also be used to convert from binary to 
 2400  decimal, but to do this we need to simulate doubling 
 2410  in a |εdecimal |πnumber system. This idea is 
 2418  generally most suitable for incorporation into 
 2424  computer hardware; however, it is possible to 
 2431  program the doubling process for decimal numbers, 
 2438  using binary addition, shifting, and extraction 
 2444  (``logical |¬a|¬n|¬d'' on each bit in the register), 
 2452  as shown in Table 1.|'{A22}{H8L10}|∨T|∨a|∨b|∨l|∨e 
 2458  |∨1|;{A4}{H9L11}DOUBLING A BINARY-CODED DECIMAL 
 2463  NUMBER|;{A6}|∂!!!!!!!|9|3|∂!!!!!!!!!!!!!!!!!!|∂!!!!!!!!!!!!!
 2464  |∂|E|;|>!|6|εOperation|'General form!!|;Example|;
 2470  >{A2}|>|π1.|9Given|'!|9|εu|β1|2u|β2|2u|β3|3u|β4|2|9u|β5|2u|β
 2473  6|2u|β7|2u|β8|2|9u|β9|2|9u|β1|β0|2u|β1|β1|2u|β1|β2|'
 2474  !|10011|90110|91001|4α=↓|43|96|99|'>|>!|6|πnumber|'
 2478  >|>2.|9Add 3 to|'!|9|εv|β1|2v|β2|2v|β3|2v|β4|2|9v|β5|2v|β6|2
 2483  v|β7|2v|β8|2|9v|β9|2|9v|β1|β0|2v|β1|β1|2v|β1|β2|'
 2484  !|10110|91001|91100|'>|>!|6|πeach digit|'>|>3.|9Shift 
 2492  left|'|εv|β1|2|9v|β2|2v|β3|2v|β4|2v|β5|2|9v|β6|2v|β7|2v|β8|2
 2493  v|β9|2|9v|β1|β0|5v|β1|β1|2v|β1|β2|20|'0|91101|90011|91000|'
 2495  >|>!|6|πone|'>|>4.|9Extract low|'|εv|β1|2|90|4|40|4|40|4|4v|
 2502  β5|2|90|4|40|4|40|4|4v|β9|2|90|9|50|9|50|9|50|'
 2503  0|90001|90001|90000|'>|>!|6|πbit|'>|>5.|9Shift 
 2510  right|'!|90|4|4|εv|β1|20|4|40|9|4|40|4|4v|β5|20|4|40|4|4|90|
 2511  4|4|9v|β9|4|40|9|50|'!|10000|90100|90100|'>|>
 2515  !|6|πtwo|'>|>6.|9Shift right|'!|90|4|4v|β1|2v|β1|20|4|4|90|4
 2520  |4v|β5|2v|β5|20|4|4|90|4|4|9v|β9|4|4v|β9|4|40|'
 2521  !|10000|90110|90110|'>|>!|6one and add|'>|>7.|9Add 
 2530  result|'|≤⊂!|≤⊂|9|≤⊂|9|≤⊂|9|≤⊂|9|9|≤⊂|9|≤⊂|9|≤⊂|9|≤⊂|9|9|≤⊂|
 2531  9|9|≤⊂|9|6|≤⊂|1|9|50|'0|91101|91001|91110|'>|>
 2535  !|6of step 3|'>|>8.|9Subtract 6|'|εy|β1|2|9y|β2|2y|β3|2y|β4|
 2542  2y|β5|2|9y|β6|2y|β7|2y|β8|2y|β9|9|2y|β1|β0|2y|β1|β1|2y|β1|β2
 2542  |20|'0|90111|90011|91000|4α=↓|47|93|98|'>|>!|6|πfrom 
 2547  each|'>{A25}{H10L12M29}|π!|9|7Another relaed 
 2551  idea is to keep a table of the powers of two 
 2562  in decimal form, and to add the appropriate powers 
 2571  together by simulating decimal addition. A survey 
 2578  of such bit-manipulation techniques appears in 
 2584  Section 7.1.|'!|9|7Finally, even Method (2b) 
 2590  can be used for the conversion of binary integers 
 2599  to decimal integers. We can _nd |εq as in (2), 
 2609  and then we can simulate the decimal division 
 2617  of |εq|4α+↓|41 |πby |εw, |πusing a ``halving'' 
 2624  process (exercise 10) which is similar to the 
 2632  doubling process just described, and retaining 
 2638  only the _rst |εn |πdigits to the right of the 
 2648  radix point in the answer. In this situation, 
 2656  Method (2b) does not seem to o=er advantages 
 2664  over the other three methods already discussed, 
 2671  but we have con_rmed the remark made earlier 
 2679  that at least four distinct methods are available 
 2687  for converting integers from one radix to another.|'
 2695  {A6}This method changes each individual digit 
 2701  |εd |πinto |ε{H12}({H10}(d|4α+↓|43)|4α⊗↓|42|4α+↓|40)|4α_↓|46
 2703  |4α=↓|42d |πwhen |ε0|4|¬E|4d|4|¬E|44, |πand into 
 2708  |ε{H12}({H10}(d|4α+↓|43)|4α⊗↓|42|4αt↓|46{H12}){H10}|4α_↓|46|
 2708  4α=↓|4(2d|4α_↓|410)|4α+↓|42|g4 |πwhen |ε5|4|¬E|4d|4|¬E|4q; 
 2711  |πand that is just what is needed to double decimal 
 2721  numbers encoded with 4 bits per digit.|'{A6}!|9|7Method 
 2729  (1b) is the most practical method for decimal-to-binary 
 2737  conversion in the great majority of cases. Here 
 2745  it is in |¬m|¬i|¬x code, assuming that there 
 2753  are at least two digits in the number |ε(u|βm|4.|4.|4.|4u|β1
 2761  u|β0)|β1|β0 |πbeing converted:|'{A8}{H9L11}|h|¬1|¬h!|∂|¬s|¬l
 2764  |¬a|¬x!|¬i|¬n|¬p|¬u|¬t|¬,|¬1!!|∂Repeat for |εm|4|¬Q|4j|4|¬Q|
 2766  40.|E|n|;|π|L|L|¬e|¬n|¬t|¬1|L|¬m|≤*/|¬1|LSet |εj|4|¬L|4m|4α_↓
 2768  |41.>|L|L|π|¬l|¬d|¬a|L|¬i|¬n|¬p|¬u|¬t|≤%|¬m|LSet 
 2770  |εU|4|¬L|4u|βm.>|π|L|¬1|¬h|L|¬m|¬u|¬l|L|≤$|¬1|¬0|≤*/>
 2772  |L|L|¬s|¬l|¬a|¬x|L|¬5>|L|L|¬a|¬d|¬d|L|¬i|¬n|¬p|¬u|¬t|¬,|¬1|L
 2773  |εU|4|¬L|410U|4α+↓|4u|βj.>|π|L|L|¬d|¬e|¬c|¬1|L|¬1>
 2775  |L|L|¬j|¬i|¬n|¬n|L|¬1|¬b|LRepeat for |εm|4|¬Q|4j|4|¬R|40.|J!
 2777  (6)>{A10}{H10L12}|πNote again that adding and 
 2783  shifting may be substituted for multiplication 
 2789  by 10.|'!|9|7A trickier but perhaps faster method, 
 2797  which uses about lg|4|εm |πmultiplications, extractions, 
 2803  and additions instead of |εm |πmultipliations 
 2809  and additions, is described in exercise 19.|'
 2816  !|9|7For the conversion of decimal fractions 
 2822  (0.|εu|βα_↓|β1u|βα_↓|β2|4.|4.|4.|4u|βα_↓|βm)|β1|β0, 
 2823  |πwe can use Method (2b), or, more commonly, 
 2831  we can convert the integer |ε(u|βα_↓|β1u|βα_↓|β2|4.|4.|4.|4u
 2836  |βα_↓|βm)|β1|β0 |πby Method (1b) and then divide 
 2843  by 10|ε|gm.|'{A12}|π|≡C|≡.|9|≡H|≡a|≡n|≡d |≡c|≡a|≡l|≡c|≡u|≡l|
 2846  ≡a|≡t|≡i|≡o|≡n|≡.|9|4Occasionally, it is necessary 
 2850  for computer programmers to convert numbers by 
 2857  hand, and since this is a subject not yet taught 
 2867  in elementary schools, it may be worth while 
 2875  to examine it brie⊗y here. There are very simple 
 2884  pencil-and-paper methods for converting between 
 2889  decimal and octal notations, and these methods 
 2896  are easily learned, so they ought to be more 
 2905  widely known.|'{A12}|εConverting octal integers 
 2910  to decimal.|9|4|πThe simplest conversion is from 
 2916  octal to decimal; this technique was apparently 
 2923  _rst published by Walter Soden, |εMath. Comp. 
 2930  |≡7 (1953), 273<274. |πTo do the conversion, 
 2937  write down the given octal number; then at the 
 2946  |εk|πth step, double the |εk |πleading digits 
 2953  using decimal arithmetic, and subtract this from 
 2960  the |εk|4α+↓|41 |πleading digits using decimal 
 2966  arithmetic. The process terminates in |εn|4α_↓|41 
 2972  |πsteps if the given number has |εn |πdigits. 
 2980  It is a good idea to insert a radix point to 
 2991  show which digits are being doubled, as shown 
 2999  in the examples given here, in order to prevent 
 3008  embarrassing mistakes.|'{A6}|≡E|≡x|≡a|≡m|≡p|≡l|≡e 
 3011  |≡1|≡.|9|4Convert (5325121)|β8 to decimal.|'{A9}!|9|∂5|2.|23
 3015  |92|95|91|92|91|'| |→α_↓|91|90>{B2}!|9##|'|L4|93|2.|22|95|91
 3018  |92|91>| |→α_↓|9|9|1|98|96>{B2}!|9##|'|L3|94|96|2.|25|91|92|
 3021  91>| |→α_↓|9|9|1|96|99|92>{B2}!|9####|'|L2|97|97|93|2.|21|92
 3024  |91>| |→α_↓|9|9|1|95|95|94|96>{B2}!|9####|'|L2|92|91|98|95|2
 3027  .|22|91>| |→α_↓|9|9|1|94|94|93|97|90>{B2}!|9#####|'
 3030  |L1|97|97|94|98|92|2.|21>| |→α_↓|9|9|1|93|95|94|99|96|94>
 3032  {B2}!|9#######|'|L1|94|91|99|98|95|97>|L!!!!!!!|εAnswer|*/:|\
 3034   (1419857)|β1|β0.>{A9}|π!|9|7A reasonably good 
 3039  check on the computations may be had by ``casting 
 3048  out mines'': The sum of the digits of the decimal 
 3058  number must equal the alternating sum and di=erence 
 3066  of the digits of the octal number, with the rightmost 
 3076  digit of the latter given a plus sign, except 
 3085  for a multiple of nine. In the above example, 
 3094  we have 1|4α+↓|44|4α+↓|41|4α+↓|49|4α+↓|48|4α+↓|45|4α+↓|47|4α
 3096  =↓|435, and 1|4α_↓|42|4α+↓|41|4α_↓|45|4α+↓|42|4α_↓|43|4α+↓|4
 3098  5|4α=↓|4|→α_↓1, and the di=erence is 36 (a multiple 
 3106  of 9). If this test fails, it can be applied 
 3116  to the |εk|4α+↓|41 |πleading digits after the 
 3123  |εk|πth step, and the error can be located using 
 3132  a ``binary search'' procedure; i.e., start by 
 3139  checking the middle result, then use the same 
 3147  procedure on the _rst or second half of the calculation, 
 3157  depending on whether the middle result is incorrect 
 3165  or correct.|'!|9|7Of course, the ``casting-out-nines'' 
 3171  process is only about 89 percent reliable; !|9|7Of 
 3179  course, the ``casting-out-nines'' process is 
 3184  only about 89 percent reliable; an even better 
 3192  check is to convert the answer back to octal 
 3201  by using an inverse method, which we will now 
 3210  consider.|'{A12}|εConverting decimal integers 
 3214  to octal.|9|4|πA similar procedure can be used 
 3221  for the opposite conversion: Write down the given 
 3229  decimal number; at the |εk|πth |πstep, double 
 3236  the |εk |πleading digits using |εoctal |πarithmetic, 
 3243  and |εadd |πthese to the |εk|4α+↓|41 |πleading 
 3250  digits using |εoctal |πarithmetic. The process 
 3256  terminates in |εn|4α_↓|41 |πsteps if the given 
 3263  number has |εn |πdigits.|'{A6}|≡E|≡x|≡a|≡m|≡p|≡l|≡e 
 3268  |≡2|≡.|9|4Convert (1419857)|β1|β0 to octal.|'
 3272  {A6}!!!!!!!!|∂1|2.}24|91|99|98|95|97|'|L!|12>
 3274  {B2}|L##>|L1|96|2.|21|99|98|95|97>|L!|13|94>{B2}!!!!!!!!###|
 3277  '|L2|91|95|2.|29|98|95|97>|L!|14|93|92>{B2}!!!!!!!!####|'
 3281  |L2|96|91|93|2.|28|95|97>|L!|15|94|92|96>{B2}!!!!!!!!####|'
 3284  |L3|93|95|96|96|2.|25|97>|L!|16|97|93|95|94>!!!!!!!!#####|'
 3287  |L4|92|95|92|94|91|2.|27>|L1|90|95|92|95|90|92>
 3289  {B2}!!!!!!!!######|'|L5|93|92|95|91|92|91>{A6}{M13}(Note 
 3292  that the nonoctal digits 8 and 9 center into 
 3301  this octal cmputation.) The answer can be checked 
 3309  as discussed above. This method was published 
 3316  by Charles P. Rozier, |εIEEE Trans. |π|≡C|≡E|≡-|≡1|≡1 
 3323  (1962), 708<709.|'{A60}|εAnswer|*/:|\ (5325121)|β8.|'
 3327  {A9}{H10L12M29}!|9|7|πThe two procedures just 
 3331  given are essentially Method (1b) of the general 
 3339  radix conversion procedures. Doubling and subtracting 
 3345  in decimal notation is like multiplying by 10|4α_↓|42|4α=↓|4
 3352  8; doubling and adding in octal notation is like 
 3361  multiplying by 8|4α+↓|42|4α=↓|410. There is a 
 3367  similar method for hexadecimal/decimal conversions, 
 3372  but it is a little more di∃cult since it involves 
 3382  multiplication by 6 instead of by 2.|'!|9|7To 
 3390  keep these two methods straingt in our minds, 
 3398  it is not hard to remember that we must subtract 
 3408  to go fr{U0}{H10L12M29}|π58320#Computer Programming!(Knuth/A
folio 407 galley 3
 3411  ddison-Wesley)!f. 407!ch. 4!g. 3(c)|'{A12}|εConverting 
 3416  fractions.|9|4|πNo equally fast method of converting 
 3422  fractions manually is known; the best way seems 
 3430  to be Method (2a), with doubling and adding or 
 3439  subtracting to simplify the multiplications by 
 3445  10 or by 8. In this case, we reverse the addition-subtractio
 3455  n criterion, adding when we convert to decimal 
 3463  and subtracting when we convert to octal; we 
 3471  also use the radix of the given input number, 
 3480  |εnot |πthe radix of the answer, in this computation 
 3489  (see Examples 3 and 4). The process is about 
 3498  twice as hard as the above method for integers.|'
 3507  {A12}{M11.6}|≡E|≡x|≡a|≡m|≡p|≡l|≡e |≡3|≡.|9|4Convert 
 3509  (.14159)|β1|β0 to octal.|'{A6}.|21|94|91|95|99|'
 3513  |7!|12|98|93|91|98|→α_↓|'{B2}#####|'|71|2.|21|93|92|97|92|'
 3516  |7|9|1|9!|12|96|95|94|94|→α_↓|'{B2}!|9#####|'
 3518  !|4|41|2.|20|96|91|97|96|'!!!|11|92|93|95|92|→#|'
 3520  {B2}!!|9#####|'!!|90|2.|24|99|94|90|98|'!!!!|99|98|98|91|96|
 3522  →α_↓|'{B2}!!!|9|1#####|'!!!|9|13|2.|29|95|92|94|96|'
 3525  !!!|9|1!|11|99|90|95|92|98|→α_↓|'{B2}!!!!|9|2#####|'
 3527  !!!!|9|27|2.|26|92|91|91|92|'!!!!|9|2!|11|92|94|92|92|94|→α_
 3528  ↓|'!!!!|9|2!|1#####|'!!!!!|9|34|2.|29|96|98|99|96|'
 3531  {A6}|εAnswer|*/:|\|9(.110374|4.|4.|4.)|β8.|'{A6}|π|≡E|≡x|≡a|≡
 3532  m|≡p|≡l|≡e |≡4|≡.|9|4Convert (.110374)|β8 to 
 3536  decimal.|'{A6}.|21|91|90|93|97|94|'!|4|42|92|90|97|97|90|→α+
 3538  ↓|'{B2}|7#####|'|71|2.|23|92|94|97|93|90|'!!|26|95|91|96|96|
 3541  90|→α+↓|'{B2}!|4|4######|'!|4|44|2.|21|92|91|91|96|90|'
 3544  !!!|32|94|92|93|94|90|→α+↓|'{B2}!!|2######|'!!|21|2.|24|95|9
 3546  4|91|94|90|'!!!|31|91|93|90|93|90|90|→α+↓|'{B2}!!!|3#######|
 3548  '!!!|35|2.|26|97|91|97|90|90|'!!!!|9|1|41|95|96|93|96|90|90|
 3550  →α+↓|'{B2}!!!!|9|1|4#######|'!!!!|9|1|48|2.|25|90|92|96|90|9
 3552  0|'!!!!!|9|1|51|92|90|95|94|90|90|→α+↓|'{B2}!!!!!|9|1|5#####
 3554  ##|'!!!!!|9|1|56|2.|22|93|93|94|90|90|'{A6}|εAnswer|*/:|\ 
 3557  (.141586|4.|4.|4.)|β1|β0.|'{H10L12M29}{B2}|J#>
 3559  {A6}|π|≡D|≡.|9|≡F|≡l|≡o|≡a|≡t|≡i|≡n|≡g|≡-|≡p|≡o|≡i|≡n|≡t 
 3560  |≡c|≡o|≡n|≡v|≡e|≡r|≡s|≡i|≡o|≡n|≡.|9|4When ⊗oating-point 
 3562  values are to be converted, it is necessary to 
 3571  deal with both the exponent and the fraction 
 3579  parts simultaneously, since conversion of the 
 3585  exponent will a=ect the fraction part. Given 
 3592  the number |εf|4|¬O|42|ge |πto be converted to 
 3599  decimal, we may express |ε2|ge |πin the form 
 3607  |εF|4|¬O|410|gE |π(usually by means of auxiliar 
 3613  tables), and then convert |εFf |πto decimal. 
 3620  Alternatively, we can multiply |εe |πby log|β1|β0|42 
 3627  and round this to the nearest integer |εE; |πthen 
 3636  divide |εf|4|¬O|42|ge |πby 10|ε|gE |πand convert 
 3642  the result. Conversely, given the number |εF|4|¬O|410|gE 
 3649  |πto be converted to binary, we may convert |εF 
 3658  |πand then multiply it by the ⊗oating-point number 
 3666  10|ε|gE |π(again commonly obtained by using tables). 
 3673  Obvious techniques may be used to reduce the 
 3681  maximum size of the auxiliary tables by using 
 3689  several multiplications and/or divisions, although 
 3694  this can cause rounding errors to propagate.|'
 3701  {A12}|≡E|≡.|9|≡M|≡u|≡l|≡t|≡i|≡p|≡l|≡e|≡-|≡p|≡r|≡e|≡c|≡i|≡s|≡
 3701  i|≡o|≡n |≡c|≡o|≡n|≡v|≡e|≡r|≡s|≡i|≡o|≡.|9|4When 
 3703  converting multiple-precision numbers, it is 
 3708  most convenient to start by converting blocks 
 3715  of digits, which can be handled by singe-precision 
 3723  techniques, then to combine them using simple 
 3730  multiple-precision techniques. For example, suppose 
 3735  that 10|ε|gn |πis the highest power of 10 less 
 3744  than the computer word size. Then|'{A12}|π!|9|7a)|9To 
 3751  convert a multiple-precision |εinteger |πfrom 
 3756  binary to decimal, divide repeatedly by 10|ε|gn 
 3763  |π(thus converting from binary to radix 10|ε|gn 
 3770  |πby Method (1a)). Single-precision operations 
 3775  will give the |εn |πdecimal digits for each place 
 3784  of the radix 10|ε|gn |πrepresentation.|'!|9|7b)|9To 
 3790  convert a multiple-precision |εfraction |πfrom 
 3795  binary to decimal, proceed similarly, multiplying 
 3801  by 10|ε|gn |π(i.e., using Method (2a) with |εB|4α=↓|410|gn).
 3808  |'|π!|9|7c)|9To convert a multiple-precision 
 3813  integer from decimal to binary, convert blocks 
 3820  of |εn |πdigits _rst; then convert from radix 
 3828  10|ε|gn |πto binary by using Method (1b).|'!|9|7d)|9Finally,
 3835   a multiple-precision fraction may be converted 
 3842  from decimal to binary by a technique similar 
 3850  to (c), using Method (2b).|'{A12}|≡F|≡.|9|≡H|≡i|≡s|≡t|≡o|≡r|
 3855  ≡y |≡a|≡n|≡d |≡B|≡i|≡b|≡l|≡i|≡o|≡g|≡r|≡a|≡p|≡h|≡y|≡.|9|4Radi
 3857  x conversion techniques implicitly originated 
 3862  in ancient problems dealing with weights, measures, 
 3869  and currencies, when a mixed radix system was 
 3877  generally involved. Auxiliary tables were usually 
 3883  used as an aid to conversion. During the seventeenth 
 3892  century when sexagesimal fractions were being 
 3898  supplanted by decimal fractions, it was necessary 
 3905  to convert between the two systems in order to 
 3914  use existing books of tables; a systematic method 
 3922  to transform fractions from radix 60 to radix 
 3930  10 and vice versa was given in the 1667 edition 
 3940  of William Oughtred's |εClavis Mathematic|9|4, 
 3945  |πChapter 6, Section 18. (This material was not 
 3953  present in the original 1631 edition of Oughtred's 
 3961  book.) Conversion rules had been given already 
 3968  by al-Kash|=7↓|Z of Persia in his |εkey to Arithmetic 
 3977  |π(c. 1414), where Methods (1a), (1b), and (2a) 
 3985  are clearly explained |ε[Istoriko-Mat. Issled. 
 3990  |≡7 (1954), 126<135], |πbut his work was unknown 
 3998  in Europe. The 18th century American mathematician 
 4005  Hugh Jones used the words ``octavation'' and 
 4012  ``decimation'' to describe octal/decimal conversions, 
 4017  but his methods were not as clever as his terminology. 
 4027  A. M. Legendre [|εTh|=1eorie des nombres |π(Paris, 
 4034  1798), 229] noted that positive integers may 
 4041  be conveniently converted to binary form by repeatedly 
 4049  dividing by 64.|'!|9|7In 1946, H. H. Goldstine 
 4057  and J. von Neumann gave prominent consideration 
 4064  to radix conversion in their classic memoir, 
 4071  ``Planning and coding problems for an electronic 
 4078  computing instrument,'' because it was necessary 
 4084  to justify the use of binary arithmetic; see 
 4092  John von Neumann, |εCollected Works |≡5 |π(New 
 4099  York: Macmillan, 1963), 127<142. Another early 
 4105  discussion of radix conversion on binary computers 
 4112  was published by F. Koons and S. Lubkin, |εMath. 
 4121  Comp. |≡3 |π(1949), 427<431, where a rather unusual 
 4129  method is suggested. The _rst discussion of ⊗oating-point 
 4137  conversion was given somewhat later by F. L. 
 4145  Bauer and K. Samelson |ε[Zeit. f|=4ur angewandte 
 4152  Math. und Physik |≡4 |π(1953), 312<316].|'!|9|7The 
 4159  following articles may be useful for further 
 4166  reference: A note by G. T. Lake |ε[CACM |≡5 |π(1962), 
 4176  468<469] mentions some hardware techniques for 
 4182  conversion and gives clear examples. A. H. Stroud 
 4190  and D. Secrest |ε[Comp. J. |≡6 |π(1963), 62<66] 
 4198  have discussed conversion of multiple-precision 
 4203  ⊗oating-point numbers. The conversion of |εunnormalized 
 4209  |π⊗oating-point numbers, preserving the amount 
 4214  of ``signi_cance'' implied by the representation, 
 4220  has been discussed by H. Kanner |ε[JACM |≡1|≡2 
 4228  (1965), 242<246] |πand by N. Metropolis and R. 
 4236  L. Ashenhurst |ε[Math. Comp |≡1|≡9 (1965), 435<441]. 
 4243  |πSee also K. Sikdar, |εSankhy|=3a |π|≡3|≡0|≡B 
 4249  (1968), 315<334, and the references he cites.|'
 4256  {A24}|*/|\|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A11}{H9L11}|9|1|≡1|≡.
 4257  |9|4[|*/|↔P|↔C|\] Generalize Method (1b) so that 
 4263  it works with mixed-radix notations, converting|'
 4269  {A9}|εa|βmb|βm|βα_↓|β1|4.|4.|4.|4b|β1b|β0|4α+↓|4|¬O|4|¬O|4|¬
 4269  O|4α+↓|4a|β1b|β0|4α+↓|4a|β0!|πinto!|εA|βMB|βM|βα_↓|β1|4.|4.|
 4269  4.|4B|β1B|β0|4α+↓|4|¬O|4|¬O|4|¬O|4α+↓|4A|β1B|β0|4α+↓|4A|β0,|
 4269  ;{A9}|πwhere 0|4|¬E|4|εa|βj|4|¬W|4b|βj, 0|4|¬E|4A|βJ|4|¬W|4B
 4272  |βJ |πfor |ε0|4|¬E|4j|4|¬W|4m, 0|4|¬E|4J|4|¬W|4M.|'
 4276  |π!!|2Give an example of your generalization 
 4282  by manually converting the quantity ``3 days, 
 4289  9 hours, 12 minutes, and 37 seconds'' into long 
 4298  tons, hundredweights, stones, pounds, and ounces. 
 4304  (Let one second equal one ounce. The British 
 4312  system of weights has 1 stone|4α=↓|414 pounds, 
 4319  1 hundredweight|4α=↓|48 stone, 1 long ton|4α=↓|420 
 4325  hundredweight.) In other words, let |εb|β0|4α=↓|460, 
 4331  b|β1|4α=↓|460, b|β2|4α=↓|424, m|4α=↓|43, B|β0|4α=↓|416, 
 4335  B|β1|4α=↓|414, B|β2|4α=↓|48, B|β3|4α=↓|420, M|4α=↓|44; 
 4339  |πthe problem is to _nd |εA|β4,|4.|4.|4.|4, A|β0 
 4346  |πin the proper ranges such that |ε3b|β2b|β1b|β0|4α+↓|42b|β1
 4352  b|β0|4α+↓|412b|β0|4α+↓|437|4α=↓|4A|β4B|β3B|β2B|β1B|β0|4α+↓|4
 4352  A|β3B|β2B|β1B|β0|4α+↓|4A|β2B|β1B|β0|4α+↓|4A|β1B|β0|4α+↓|4A|β
 4352  0, |πusing a systematic method which generalizes 
 4359  Method (1b). (All arithmetic is to be done in 
 4368  a mixed-radix system.)|'{A3}|9|1|≡2|≡.|9|4[|*/|↔P|↔C|\] 
 4372  Generalize Method (1a) so that it works with 
 4380  mixed-radix notations, as in exercise 1, and 
 4387  give an example of your generalization by manually 
 4395  solving the same conversion problem stated in 
 4402  exercise 1.|'{A3}|9|1|≡3|≡.|9|4[|*/|↔P|↔C|\] (D. 
 4406  Taranto.) The text observes that when fractions 
 4413  are bing converted, there is in general no obvious 
 4422  way to decide how many digbits to give in the 
 4432  answer. Design a simple generalization of Method 
 4439  (2a) which, given two positive radix |εb |πfractions 
 4447  |εu |πand |ε|≤o |πbetween 0 and 1, converts |εu 
 4456  |πto a radix |εB |πequivalent |εU |πwhich has 
 4464  just enouth places of accuracy to ensure that 
 4472  |ε|¬GU|4α_↓|4u|¬G|4|¬W|4|≤o. |π(If |εu|4|¬W|4|≤o, 
 4475  |πwe may take |εU|4α=↓|40, |πwith zero ``places 
 4482  of accuracy.'')|'{A3}|9|1|≡4|≡.|9|4[|εM|π|*/|↔P|↔O|\] 
 4485  (a) Prove that every real number which has a 
 4494  terminating |εbinary |πrepresentation also has 
 4499  a terminating |εdecimal |πrepresentation. (b) 
 4504  Find a simpl condition on the positive integers 
 4512  |εb |πand |εB, |πwhich is satis_ed if and only 
 4521  if every real number which has a teminatiing 
 4529  radix |εb |πrepresentation also has a terminating 
 4536  radix |εB |πrepresentation.|'{A3}|9|1|≡5|≡.|9|4[|εM|π|*/|↔P|↔
 4539  c|\] Show that program (4) would work also if 
 4548  the instruction ``|¬l|¬d|¬x|≤$|¬1|¬0|g|¬n|≤$'' 
 4551  were replaced by ``|¬l|¬d|¬x |≤$|εc|≤$'' |πfor 
 4557  certain other constants |εc.|'{A3}|9|1|π|≡6|≡.|9|4[|*/|↔L|↔c|
 4561  \] Discuss using Methods (1a), (1b), (2a), and 
 4569  (2b) when |εb |πor |εB |πis |→α_↓2.|'{A3}|9|1|≡7|≡.|9|4[|εM|
 4576  π|*/|↔O|↔l|\] Given that 0|4|¬W|4|ε|≤a|4|¬E|4x|4|¬E|4|≤a|4α+↓
 4579  |41/w |πand 0|4|¬E|4|εu|4|¬E|4w, |πprove that 
 4584  |"l|εux|"L|4α=↓|4|"l|≤au|"L |πor |ε|"l|≤au|"L|4α+↓|41. 
 4587  |πFurthermore |ε|"lux|"L|4α=↓|4|"l|≤ax|"L |πexactly, 
 4590  if |εu|4|¬W|4|≤aw |πand |ε|≤a|gα_↓|g1 |πis an 
 4596  integer.|'{A3}|9|1|≡8|≡.|9|4[|*/|↔P|↔M|\] Write 
 4599  a |¬m|¬i|¬x program analogous to (1) which uses 
 4607  (5) and which does not include any division instructions.|'
 4616  {A3}|9|1|≡9|≡.|9|4[|εM|π|*/|↔P|↔p|\] Let |εu |πbe 
 4620  an integer, 0|4|¬E|4|εu|4|¬W|42|g3|g4. |πAssume 
 4624  that the following sequence of operations (equivalent 
 4631  to addition and binary ``shift-right'' instructions) 
 4637  is performed:|'{A6}|h|ε|∂v|4|¬L|4v|4α+↓|4|"l2|gα_↓|g8v|"L,!!
 4639  |∂v|4|¬L|4v|4α+↓|4|"l2|gα_↓|g1|g6v|"L,!!|∂v|4|¬L|4v|4α+↓|4|"
 4639  l2|gα_↓|g4v|"L,|E|n|;|Lv|4|¬L|4|"l|f1|d32|)u|"L,|Lv|4|¬L|4v|
 4640  4α+↓|4|"l|f1|d32|)|"L,|Lv|4|¬L|4v|4α+↓|4|"l2|gα_↓|g4v|"L,>
 4641  {A4}|Lv|4|¬L|4v|4α+↓|4|"l2|gα_↓|g8v|"L,|Lv|4|¬L|4v|4α+↓|4|"l
 4641  2|gα_↓|g1|g6v|"L,|Lv|4|¬L|4|"l|f1|d38|)v|"L.>
 4642  {A6}|πProve that |εv|4α=↓|4|"lu/10|"L |πor |ε|"lu/10|"L|4α_↓
 4646  |41.|'{A3}|π|≡1|≡0|≡.|9|4[|*/|↔P|↔P|\] The text 
 4650  shows how a binary-coded decimal number can be 
 4658  doubled by using various shifting, extracting, 
 4664  and addition operations on a binary computer. 
 4671  Give an analogous method which computes |εhalf 
 4678  |πof a binary-coded decimal number (throwing 
 4684  away the remainder if the number is odd).|'|Hβ*?*?*?*!*!*!*!*!*!*!*!*!*!*!
 4692  
folio 411 galley 4
       {U0}{H10L12M29}|π58320#Computer Programming!(Knuth/Ad
 1041  dison-Wesley)!f. 411!ch. 4!g. 4c|'{A6}|≡1|≡1|≡.|9|4[|*/|↔O|↔o
 1045  |\] Convert (57721)|β8 to decimal.|'{A3}|≡1|≡2|≡.|9|4[|*/|↔P|
 1050  ↔P|\] Invent a rapid pencil-and-paper method 
 1056  for converting integers from ternary notation 
 1062  to decimal, and illustrate your method by converting 
 1070  (1212011210210)|β3 into decimal. How would you 
 1076  go fromdecimal to ternary?|'{A3}|≡1|≡3|≡.|9|4[|*/|↔P|↔C|\] 
 1081  Assume that locations |¬u|4α+↓|41, |¬u|4α+↓|42,|4.|4.|4.|4, 
 1086  |¬u|4α+↓|4|εm |πcontain a multiple-precision 
 1090  fraction |ε(.u|βα_↓|β1u|βα_↓|β2|4.|4.|4.|4j|βα_↓|βm)|βb, 
 1092  |πwhere |εb |πis the word size of |¬m|¬i|¬x|¬. 
 1100  Write a |¬m|¬i|¬x routine which converts this 
 1107  fraction to decimal notation, truncating it to 
 1114  180 decimal digits. The answer should be printed 
 1122  on two lines, with the digits grouped into 20 
 1131  blocks of nine each separated by blanks. (Use 
 1139  the |¬c|¬h|¬a|¬r instruction.)|'{A3}|≡1|≡4|≡.|9|4[|εM|π|*/|↔P
 1142  |↔p|\] (A. Sch|=4onhage.) The text's method of 
 1149  converting multiple-precision integers requires 
 1153  an execution time of order |εn|g2 |πto convert 
 1161  an |εn-|πdigit integer, when |εn |πis large. 
 1168  Show that it is possible to convert |εn-|πdigit 
 1176  decimal integers into binary notation in |εO{H11}({H9}M(n)|π
 1182  log|4|εn{H11}){H9} |πcycles, where |εM(n) |πis 
 1187  an upper bound on the number of cycles needed 
 1196  to multiply |εn-|πbit binary numbers which represents 
 1203  the best |εp-|πdigit base |εb |π⊗oating-point 
 1209  approximation to |εu, |πin the sense of Section 
 1217  4.2.2. Under the assumption that log|ε|βB|4b 
 1223  |πis irrational and that the range of exponents 
 1231  is unlimited, prove that |'{A9}|εu|4α=↓|4|πround|ε|βb{H11}({
 1236  H9}|πround|ε|βB(u,|4P),|4p{H11}){H9},|;{A9}|πfor 
 1238  all |εp-|πdigit base |εb |π⊗oating-point numbers 
 1244  |εu, |πif and only if |εB|gp|gα_↓|g1|4|¬R|4b|gp. 
 1250  |π(In othert words, an ``ideal'' input conversion 
 1257  of |εu |πinto an independent base |εB, |πfollowed 
 1265  by an ``ideal'' output conversion of this result, 
 1273  will always yield |εu |πagain if and only if 
 1282  the intermediate precision |εP |πis suitably 
 1288  large, as speci_ed by the formula above.)|'{A3}|≡1|≡9|≡.|9|4
 1295  [|εM|π|*/|↔P|↔L|\] Let the decimal number |εu|4α=↓|4(u|β7|4.|
 1300  4.|4.|4u|β1u|β0)|β1|β0 |πbe represented as the 
 1305  binary-coded decimal number |εU|4α=↓|4(u|β7|4.|4.|4.|4u|β1u|
 1308  β0)|β1|β6. |πFind appropriate constants |εc|βi 
 1313  |πand masks |εm|βi |πso that the operation |εU|4|¬L|4U|4α_↓|
 1320  4c|βi(U|4|↔i|4m|βi), |πrepeated for |εi|4α=↓|41, 
 1324  2, 3, |πwill convert |εU |πto the binary representation 
 1333  of |εu, |πwhere ``|→|↔i'' |πdenotes extraction 
 1339  (i.e., ``logical |¬a|¬n|¬d'' on individual bits).|'
 1345  {A25}{H10L12}|∨4|∨.|∨5|∨.|9|∨R|∨A|∨T|∨I|∨O|∨N|∨A|∨L|9|∨A|∨R|
 1345  ∨I|∨T|∨H|∨M|∨E|∨T|∨I|∨C|'{A12}|∨4|∨.|∨5|∨.|∨1|∨.|9|∨F|∨r|∨a|
 1346  ∨c|∨t|∨i|∨o|∨n|∨s|'{A6}In many numerical algorithms 
 1351  it is important to know that the answer to a 
 1361  problem is exactly |f1|d33|), not a ⊗oating-point 
 1368  number which gets printed as ``0.333333574''. 
 1374  If arithmetic is done on fractions instead of 
 1382  on approximations to fractions, many computations 
 1388  can be done entirely |εwithout any accumulated 
 1395  rounding errors. |πThis results in a comfortable 
 1402  feeling of security which is often lacking when 
 1410  ⊗oating-point calculations have been made, and 
 1416  it means that the accuracy of the calculation 
 1424  cannot be improved upon.|'!|9|7When fractional 
 1430  arithmetic is desired, th e numbers can be represented 
 1439  as pairs of integers, |ε(u/u|¬S), |πwhere |εu 
 1446  |πand |εu|¬S |πare relatively prime to each other 
 1454  and |εu|¬S|4|¬Q|40. |πThe number zero is represented 
 1461  as (o/1). In this form, |ε(u/u|¬S)|4α=↓|4(v/v|¬S) 
 1467  |πif and only if |εu|4α=↓|4v| |πand |εu|¬S|4α=↓|4v|¬S.|'
 1473  |π!|9|7Multiplication of fractions is, of course, 
 1479  rather simple; to form |ε(u/u|¬S)|4α⊗↓|4(v/v|¬S)|4α=↓|4(w/w|
 1483  ¬S), |πwe can simply compute |εuv |πand |εu|¬Sv|¬S. 
 1491  |πThe two products |εuv |πand |εu|¬Sv|¬S |πmight 
 1498  not be relatively prime, but if |εd|4α=↓|4|πgcd|ε(uv,|4u|¬Sv
 1504  |¬S), |πthe desired answer is |εw|4α=↓|4uv/d, 
 1510  w|¬Sα=↓u|¬Sv|¬S/d. |π(See exercise 2.) E∃cient 
 1515  algorithms to compute the greatest common divisor 
 1522  are discussed in Section 4.5.2.|'!|9|7Another 
 1528  way to perform the multiplication is to _nd |εd|β1|4α=↓|4|πg
 1536  cd|ε(u,|4v|¬S) |πand |εd|β2|4α=↓|4|πgcd|ε(u|¬S,|4v); 
 1539  |πthen the answer is |εw|4α=↓|4(u/d|β1)(v/d|β2), 
 1544  w|¬S|4α=↓|4(u|¬S/d|β2)(v|¬S/d|β1). |π(See exercise 
 1547  3.) This method requires two gcd calculations, 
 1554  but it is not really slower than the former method; 
 1564  the gcd process involves a number of iterations 
 1572  essentially proportional to the logarithm of 
 1578  its inputs, so the total number of iterations 
 1586  needed to evaluate both |εd|β1 |πand |εd|β2 |πis 
 1594  essentially the same as the number of iterations 
 1602  during the single calculation of |εd. |πFurthermore, 
 1609  each iteration in the elevation of |εd|β1 |πand 
 1617  |εd|β2 |πis potentially faster, because comparatively 
 1623  small numbers are being examined. If |εu, u|¬S, 
 1631  v, v|¬S |πare single-precision quantities, this 
 1637  method hs the advantagbe that no double-precision 
 1644  numbers appear in the calculation unless it is 
 1652  impossible to represent both of the answers |εw 
 1660  |πand |εw|¬S |πin single precision form.|'!|9|7Division 
 1667  may be done in a similar manner; see exercise 
 1676  4.|'!|9|7Addition and subtraction are slightly 
 1682  more complicated. We can set |ε(u/u|¬S)|4|¬N|4(v/v|¬S)|4α=↓|
 1687  4{H12}({H10}(uv|¬S|4|¬N|4u|¬Sv)/u|¬Sv|¬S{H12}){H10} 
 1688  |πand reduce this fraction to lowest terms by 
 1696  calculating |εd|4α=↓|4|πgcd|ε(uv|¬S|4|¬N|4u|¬Sv,|4u|¬Sv|¬S) 
 1698  |πas in the _rst multiplication method. But again 
 1706  it is possible to avoid working with such large 
 1715  numbers, if we start by calculating |εd|β1|4α=↓|4|πgcd|ε(u|¬
 1721  S,|4v|¬S). |πIf |εd|β1|4α=↓|41 |πthen |εw|4α=↓|4uv|¬S|4|¬N|4
 1725  u|¬Sv |πand |εw|¬S|4α=↓|4|¬Sv|¬S |πare the desired 
 1731  answers. (According to THhe*? fraction to lowest 
 1738  terms by calculating |εd|4α=↓|4|πgcd|ε(uv|¬S|4|¬N|4u|¬Sv,|4u
 1741  |¬Sv|¬S) |πas in the _rst multiplication method. 
 1748  But again it is possible to avoid working with 
 1757  such large numbers, if we start by calculating 
 1765  |εd|β1|4α=↓|4|πgcd|ε(u|¬S,|4v|¬S). |πIf |εd|β1|4α=↓|41 
 1768  |πthen |εw|4α=↓|4uv|¬S|4|¬N|4u|¬Sv |πand |εw|¬S|4α=↓|4|¬Sv|¬
 1771  S |πare the desired answers. (According to Theorem 
 1779  4.5.2D, |εd|β1 |πwill be 1 about 61 percent of 
 1788  the time, if the denominators |εu|¬S |πand |εv|¬S 
 1796  |πare randomly distributed, so it is wise to 
 1804  single out this case separately.) If |εd|β1|4|¬Q|41, 
 1811  |πthen let |εt|4α=↓|4u(v|¬S/d|β1)|¬N|4v(u|¬S/d|β1) 
 1814  |πand calclate |εd|β2|4α=↓|4|πgcd|ε(t,|4d|β1); 
 1817  |π_nally the answer is |εw|4α=↓|4t/d|β2, w|¬S|4α=↓|4(u|¬S/d|
 1822  β1)(v|¬S/d|β2). (|πExercise 6 proves that these 
 1828  values of |εw |πand |εw|¬S |πare relatively prime 
 1836  to each other.) If single-precision numbers are 
 1843  being used, this method requires only single-precision 
 1850  operations, except that |εt |πmay be a double-precision 
 1858  number or slightly larger (see exercise 7); since 
 1866  gcd|ε(t,|4d|β1)|4α=↓|4|πgcd(|εt|4|πmod|4|εd|β1,|4d|β1), 
 1867  |πthe calculation of |εd|β2 |πdoes not require 
 1874  double precision.|'!|9|7For example, to compute 
 1880  (7/66)|4α+↓|4(17/12), we form |εd|β1|4α=↓|4|πgcd(66,|412)|4α
 1883  =↓|46; then |εt|4α=↓|47|4|¬O|42|4α+↓|417|4|¬O|411|4α=↓|4201,
 1885   |πand |εd|β2|4α=↓|4|πgcd(201,|46)|4α=↓|43, so 
 1889  the answer is|'{A9}|f201|d33|)/|f66|d36|)|4|f12|d33|)|4α=↓|4
 1892  67/44.|'{A9}!|9|7Experience with fractional calculations 
 1897  shows that in many cases the numbers grow to 
 1906  be quite large; for example, see the remarks 
 1914  following Eq. 3.3.2<22. So if |εu |πand |εu|¬S 
 1922  |πare intended to be single-precision numbers 
 1928  for each fraction |ε(u/u|¬S), |πit is important 
 1935  to include tests for over⊗ow in each of the addition, 
 1945  subtraction, multiplication, and division subroutines. 
 1950  For numerical problems in which perfect accuracy 
 1957  is important, a set of subroutines for fractional 
 1965  arithmetic with |εarbitrary |πprecision allowed 
 1970  in numerator and denominator is very useful.|'
 1977  !|9|7The methods of this section also extend 
 1984  to other number _elds besides the rational numbers; 
 1992  for example, we could do arithmetic on quantities 
 2000  of the form |ε(u|4α+↓|4u|¬S{H11}|¬H{H10}|v45)u|¬C, 
 2004  |πwhere |εu, u|¬S, u|¬C |πare integers, gcd|ε(u,|4u|¬S,|4u|¬
 2010  C)|4α=↓|41, |πand |εu|¬C|4|¬Q|40; |πor on quantities 
 2016  of the form |ε(u|4α+↓|4u|¬S|=|g3{H11}|¬H{H10}|v42|)|4α+↓|4u|
 2019  ¬C|=|g3{H11}|¬H{H10}|v44|))/u|9|1, |πetc.|'!|9|7To 
 2022  help check out subroutines for rational arithmetic, 
 2029  inversion of matrices with known inverses (e.g., 
 2036  Cauchy matrices, exercises 111111*?*?!|9|7To help 
 2041  check out subroutines for rational arithmetic, 
 2047  inversion of matrices with known inverses (e.g., 
 2054  Cauchy matrices, exercise 1.2.3<41) is suggested.|'
 2060  !|9|7Exacty representation of fractions within 
 2065  a computer was _rst discussed in the literature 
 2073  by P. Henrici, |εJACM |≡3 (1956), 6<9.|'{A24}|π|∨E|∨X|∨E|∨R|
 2080  ∨C|∨I|∨S|∨E|∨S|'{A12}{H9L11}|9|1|≡1|≡.|9|4[|*/|↔O|↔C|\] 
 2082  Suggest a reasonable computational method for 
 2088  comparing two fractions, to test whether or not 
 2096  |ε(u/u|¬S)|4|¬W|4(v/v|¬S).|'{A3}|π|9|1|≡2|≡.|9|4[|εM|π|*/|↔O|
 2097  ↔C|\] Prove that if |εd|4α=↓|4|πgcd|ε(u,|4v) 
 2102  |πthen |εu/d |πand |εv/d |πare relatively prime.|'
 2109  {A3}|9|1|≡3|≡.|9|4[|εM|π|*/|↔P|↔c|\] Prove that 
 2112  if |εu |πand |εu|¬S |πare relatively prime, and 
 2120  if |εv |πand |εv|¬S |πare relatively prime, then 
 2128  gcd(|εuv,|4u|¬Sv|¬S)|4α=↓|4|πgcd|ε(u,|4v|¬S)|πgcd|ε(u|¬S,|4v
 2128  ).|'{A3}|9|1|π|≡4|≡.|9|4|*/|↔O|↔O|\] Design a 
 2132  division algorithm for fractions, analogous to 
 2138  the second multiplication method of the text. 
 2145  (Note that the sign of |ε|≤v |πmust be considered.)|'
 2154  {A3}|9|1|≡5|≡.|9|4[|*/|↔O|↔c|\] Compute (17/120)|4α+↓|4(|→α_↓
 2156  27/70) by the method recommended in the text.|'
 2164  {A3}|9|1|≡6|≡.|9|4[|εM|π|*/|↔P|↔L|\] Show that 
 2167  if |εu, u|¬S |πare relatively prime and if |εv, 
 2176  v|¬S |πare relatively prime, then gcd(|εuv|¬S|4α+↓|4vu|¬S,|4
 2181  u|¬Sv|¬S)|4α=↓|4d|β1d|β2 |πwhere |εd|β1|4α=↓|4|πgcd|ε(u|¬S,|
 2183  4v|¬S) |πand |εd|β2|4α=↓|4|πgcd(|εd|β1,|4u(v|¬S/d|β1)|4α+↓|4
 2185  v(u|¬S/d|β1)). |π(Hence if |εd|β1|4α=↓|41, |πthenn 
 2190  |εεεεεε*?*?|¬S/d|β1)). |π(Hence if |εd|β1|4α=↓|41, 
 2194  |πthen |εuv|¬S|4α+↓|4vu|¬S |πis relatively prime 
 2199  to |εu|¬Sv|¬S.)|'{A3}|π|9|1|≡7|≡.|9|4[|εM|π|*/|↔P|↔P|\] 
 2202  How large can the absolute value of the quantity 
 2211  |εt |πbecome, in the addition-subtraction method 
 2217  recommended in the text, if the input numerators 
 2225  and denominators are less than |εN |πin absolute 
 2233  value?|'{A3}|9|1|≡8|≡.|9|4[|*/|↔P|↔P|\] Discuss 
 2236  using (1/0) and (|→α_↓1/0) |πas rep=resentations 
 2242  for |¬X and |→α_↓|¬X, and /or as representations 
 2250  of over⊗ow.|'{A3}|π|9|1|≡9|≡.|9|4[|εM|π|*/|↔P|↔L|\] 
 2253  If 1|4|¬E|4|εu|¬S, v|¬S|4|¬W|42|gn, |πshow that 
 2258  |"l2|ε|g2|gnu/u|¬S|"L|4α=↓|4|"l2|g2|gnv/v|¬S|"L 
 2259  |πimplies |εu/u|¬S|4α=↓|4v/v|¬S.|'{A3}|π|≡1|≡0|≡.|9|4|*/|\[|*/
 2261  |↔M|↔O|\] Extend the subroutines suggested in 
 2267  exercise 4.3.1<34 so that they deal with ``arbitrary'' 
 2275  rational numbers.|'{A3}|≡1|≡1|≡.|9|4[|εM|π|*/|↔P|↔L|\] 
 2278  Consider fractions of the form |ε(u|4α+↓|4u|¬S{H11}|¬H{H9}|v
 2283  45|))/u|¬C, |πwhere |εu, u|¬S, u|¬C |πare integers, 
 2290  gcd(|εu,|4u|¬S,|4u|¬C)|4α=↓|41, |πand |εu|¬C|4|¬Q|40. 
 2293  |πExplain how to divide two such fractions and